#include <iostream>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *nxt) : val(x), next(nxt) {}
};

class Solution {
  public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode *head = nullptr, *tail = nullptr;
        const int maxint = 0x7fffffff;
        int len = lists.size(), mn = maxint, ind = -1;
        while (true) {
            ind = -1;
            mn = maxint;
            for (int i = 0; i < len; i++) {
                if (lists[i] == nullptr) continue;
                if (lists[i]->val > mn) continue;
                ind = i;
                mn = lists[i]->val;
            }
            if (ind == -1) break;
            if (head == nullptr) {
                head = tail = new ListNode(mn);
            } else {
                tail->next = new ListNode(mn);
                tail = tail->next;
            }
            lists[ind] = lists[ind]->next;
        }
        return head;
    }
};